#include <iostream>
#include <math.h>
#include <algorithm>
#include <vector>
#include <bitset>
using namespace std;
class Solution
{
public:
    /**
     * @brief 0 <= turnedOn <= 10
     *
     * @param turnedOn
     * @return vector<string> watch list
     */
    vector<string> readBinaryWatch(int turnedOn)
    {
        vector<string> res;
        vector<int> hourBits = {1, 2, 4, 8};
        vector<int> minuteBits = {1, 2, 4, 8, 16, 32};
        return res;
    }
    int binaryToDecimal(string s)
    {
        int n = s.size();
        int ans = 0;
        for (int i = n - 1; i >= 0; i--)
        {
            if (s[i] == '1')
            {
                ans += pow(2, n - 1 - i);
            };
        }
        return ans;
    }
    vector<int> hours(int n)
    {
        vector<int> ans;
        if (n > 4 || n < 0)
            return ans;
        vector<string> s;
        if (n == 0)
            s = {"0000"};
        if (n == 1)
            s = {"0001"};
        if (n == 2)
            s = {"0011"};
        if (n == 3)
            s = {"0111"};
        if (n == 4)
            s = {"1111"};
        string temp = s[0];
        while (next_permutation(temp.begin(), temp.end()))
        {
            s.push_back(temp);
        }
        for (int i = 0; i < s.size(); i++)
        {
            ans.push_back(binaryToDecimal(s[i]));
        }
        return ans;
    }
    vector<int> minutes(int n)
    {
        vector<int> ans;
        if (n > 6 || n < 0)
            return ans;
        vector<string> s;
        if (n == 0)
            s = {"000000"};
        if (n == 1)
            s = {"000001"};
        if (n == 2)
            s = {"000011"};
        if (n == 3)
            s = {"000111"};
        if (n == 4)
            s = {"001111"};
        if (n == 5)
            s = {"011111"};
        if (n == 6)
            s = {"111111"};
        string temp = s[0];
        while (next_permutation(temp.begin(), temp.end()))
        {
            s.push_back(temp);
        }
        for (int i = 0; i < s.size(); i++)
        {
            ans.push_back(binaryToDecimal(s[i]));
        }
        return ans;
    }
    vector<string> readBinaryWatch_2(int turnedOn)
    {
        vector<string> ans;
        for (int i = 0; i <= 4; i++)
        {
            if (turnedOn < i)
                continue;
            vector<int> hour = hours(i);
            vector<int> minu = minutes(turnedOn - i);
            int h = hour.size(), m = minu.size();
            string temp;
            if (h == 0 || m == 0)
                continue;
            for (int j = 0; j < h; j++)
            {
                for (int k = 0; k < m; k++)
                {
                    if (hour[j] < 12 && minu[k] < 60)
                    {
                        int tempH = hour[j];
                        int tempM = minu[k];
                        if (tempM < 10)
                            temp = to_string(tempH) + ":0" + to_string(tempM);
                        else
                            temp = to_string(tempH) + ":" + to_string(tempM);
                        ans.push_back(temp);
                    }
                }
            }
        }
        return ans;
    }

    vector<string> readBinaryWatch_3(int turnedOn)
    {
        vector<string> res;
        for (int h = 0; h < 12; h++)
        {
            for (int m = 0; m < 60; m++)
            {
                {
                    bitset<10> hhmm(h << 6 | m);
                    if (hhmm.count() == turnedOn)
                    {
                        res.emplace_back(to_string(h) + (m < 10 ? ":0" : ":") + to_string(m));
                    }
                }
            }
        }
        return res;
    }
};

int main()
{
    Solution s;
    vector<string> res = s.readBinaryWatch_3(5);
    for (string r : res)
    {
        cout << r << " ";
    }
    cout << endl;
    return 0;
}
